package graph

import (
	"container/list"
	"fmt"
	"math"
	"strings"
)

// example graph
var Relations = map[string][]string{
	"YOU" : {"BOB", "ALICE","CLIAIRE"},
	"BOB" : {"ANUJ", "PEGGY"},
	"ALICE":{"PEGGY"},
	"CLIAIRE":{"THON", "JOHNNY"},
}

func PushBack(l *list.List , es []string){
	for _, v := range es {
		l.PushBack(v)
	}
}

func PopFront(l *list.List)string{
	person, _ := l.Remove(l.Front()).(string)
	return person
}


func BFS(target string){
	search_queue := list.New()
	PushBack(search_queue, Relations["YOU"])
	searched := map[string]rune{}
	for search_queue.Len() > 0 {
		//fmt.Println(search_queue.Len(), search_queue.Front().Value,searched)
		person := PopFront(search_queue)
		if _ , ok := searched[person] ; !ok {
			// 判断人员
			if strings.Compare(person, target) == 0{
				fmt.Println(person)
				return
			}else{
				//fmt.Println(Relations[person])
				PushBack(search_queue, Relations[person])
				searched[person] = 'c'
			}
		}
	} 
}

var DJdata = map[string]map[string]int32{
	"A":{"B":5, "C":0},
	"B":{"D":15, "E":20},
	"C":{"D":30, "E":35},
	"D":{"F":20},
	"E":{"F":10},
}

func Dijkstra(start string, end string){
	cost := map[string]int32{
		end: math.MaxInt32 ,
	}
	for k := range DJdata {
		cost[k] = math.MaxInt32
	}
	parents := map[string]string{
		end : "none",
	}
	searched := map[string]rune{}
	for key, val :=range DJdata[start] {
		cost[key] = val
		parents[key] = start
	}
	var lowestCoseNode = func(m map[string]int32) string {
		min := int32(math.MaxInt32)
		ana := "none"
		for k, v := range m {
			if _, ok := searched[k] ; v < min && !ok {
				min = v
				ana = k
			}
		}
		return ana
	}

	node := lowestCoseNode(cost)
	for node != "none" {
		fmt.Println(node)
		c := cost[node]
		neighbors := DJdata[node]
		for key , v :=range neighbors {
			new_c := c + v
			fmt.Println(node, key, cost[key], new_c)
			if cost[key] > new_c {
				cost[key] = new_c
				parents[key] = node
			}
		}
		searched[node] = 'c'
		node = lowestCoseNode(cost)
	}
	temp :=  parents[end]
	for temp != start{
		fmt.Println(temp)
		temp = parents[temp]
	}
}